package com.LeeCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 串联字符串的最大长度
 */

public class Code1239 {
    public static void main(String[] args) {
        List<String> arr = new ArrayList<String>();
        arr.add("yy");
        arr.add("wmpnpm");
        System.out.println(new Code1239().maxLength(arr));
    }

    private int ans = 0;

    public int maxLength(List<String> arr) {
        int[] masks = new int[arr.size()];
        for (int i = 0; i < arr.size(); i++) {
            for (char c : arr.get(i).toCharArray()) {
                if ((masks[i] | 1 << (c - 'a')) != masks[i]) {
                    masks[i] |= 1 << (c - 'a');
                } else {
                    masks[i] = 0;
                    break;
                }
            }
        }
        backtrace(masks, 0, 0);
        return ans;
    }

    private void backtrace(int[] masks, int index, int cur) {
        if (index == masks.length) {
            ans = Math.max(ans, Integer.bitCount(cur));
            return;
        }
        // 不选
        backtrace(masks, index + 1, cur);
        if ((cur & masks[index]) == 0) { // 能选
            backtrace(masks, index + 1, cur | masks[index]);
        }
    }
}
